package br.univap.aed.cenario2.sort;

public class QuickSortIterativo {

	Integer[] vetor_sort = new Integer[0];
	private int copias;
	private int comparacoes;

	public QuickSortIterativo() {
		this.copias = 0;
		this.comparacoes = 0;
	}

	private void iterativeSort(Integer[] vetor, int esquerda, int direita) {
		int i, j;
		for (i = esquerda; i < direita; i++) {
			j = i;
			while ((vetor[j - 1] > vetor[j]) && (j > 0)) {
				comparacoes++;
				swap(vetor[j - 1], vetor[j]);
				j--;
			}
		}
	}

	private int partition(Integer[] vetor, int esquerda, int direita) {
		int i, ultimoMenor, meio, temp, pivot;

		meio = (esquerda + direita) / 2;
		temp = vetor[esquerda];
		vetor[esquerda] = vetor[meio];
		vetor[meio] = temp;
		pivot = vetor[esquerda];
		ultimoMenor = esquerda;

		for (i = esquerda + 1; i <= direita; i++) {

			if (vetor[i] < pivot) {
				comparacoes++;
				temp = vetor[++ultimoMenor];
				vetor[ultimoMenor] = vetor[i];
				vetor[i] = temp;
			}
		}
		temp = vetor[esquerda];
		vetor[esquerda] = vetor[ultimoMenor];
		vetor[ultimoMenor] = temp;

		return ultimoMenor;
	}

	public int sort(Integer[] vetor) {
		int esquerda, direita, n, pivot;
		Integer[] vetorEsquerda = new Integer[vetor.length];
		Integer[] vetorDireita = new Integer[vetor.length];

		n = 0;
		esquerda = 0;
		direita = vetor.length - 1;

		while (n >= 0) {

			while (esquerda < direita) {

				pivot = partition(vetor, esquerda, direita);

				if ((pivot - esquerda) < (direita - pivot)) {
					vetorEsquerda[n] = pivot + 1;
					vetorDireita[n] = direita;
					n = n + 1;
					direita = pivot - 1;
				} else {
					vetorEsquerda[n] = esquerda;
					vetorDireita[n] = pivot - 1;
					n = n + 1;
					esquerda = pivot + 1;
				}

			}

			if (esquerda < direita) {
				iterativeSort(vetor, esquerda, direita);
			}

			n = n - 1;
			if (n >= 0) {
				esquerda = vetorEsquerda[n];
				direita = vetorDireita[n];
			}

		}
		vetorSorted(vetor);
		return 0;
	}

	private void swap(int x, int y) {
		int temp;

		temp = x;
		x = y;
		y = temp;
	}

	private void vetorSorted(Integer[] vetor) {
		Integer[] aux = new Integer[vetor.length];

		for (int i = 0; i < vetor.length; i++) {
			aux[i] = vetor[i];
		}

		vetor_sort = aux;
		copias++;
	}

	public Integer[] getVetorSort() {
		return vetor_sort;
	}

	public void cleanVetorSort() {
		this.vetor_sort = new Integer[0];
	}

	public int getCopias() {
		return copias;
	}

	public int getComparacoes() {
		return comparacoes;
	}

}
